Алгоритм текущего ведра

Алгоритм маркерной корзины (англ. Token Bucket Algorithm) — алгоритм, позволяющий ограничить полосу пропускания канала и в то же время гарантировать некоторую скорость передачи данных (кадров или пакетов). Поскольку скорость передачи пакета по каналу всегда равна скорости передачи битового потока по среде передачи (или скорости модуляции), то для ограничения, или другими словами, уменьшения средней скорости передачи нужно увеличить временные интервалы между пакетами. Ограничение скорости достигается отбрасыванием некоторых пакетов, передача которых ведёт к превышению согласованной скорости.

Общая информация

Алгоритм текущего (или дырявого) ведра называется так по аналогии с протекающим ведром. Скорость втекания жидкости в ведро определяет согласованную скорость передачи, а скорость вытекания — реальную среднюю скорость передачи. Если отверстие в ведре настолько большое, что вся жидкость, втекающая в ведро, сразу из него вытекает, скорость вытекания не может быть больше скорости втекания. То есть реальная средняя скорость передачи никогда не превысит заданной согласованной скорости.

Задача алгоритма — принять решение: передать пакет или отбросить.

Параметрами алгоритма являются скорость поступления маркеров в «ведро» (бит/с) и объём «ведра» или «вёдер» (если в алгоритме используется два «ведра»). Один маркер может соответствовать одному биту передаваемой информации. Скорость поступления маркеров определяет среднюю согласованную скорость передачи информации (CIR — commited information rate). Данная скорость гарантируется при передаче информации. Объём «ведра» определяет согласованную величину всплеска (committed burst size (CBS) или exceed burst size (EBS), если в алгоритме используется два «ведра»).

Виды алгоритма

Алгоритм с одним ведром

В ведро с постоянной скоростью CIR помещаются маркеры. Если количество маркеров достигло объёма «ведра» CBS, то они туда больше не добавляются. Если размер пакета, который необходимо передать, больше, чем число маркеров в «ведре», то пакет отбрасывается, иначе — передаётся. При этом из ведра удаляется количество маркеров, равное длине пакета. Маркеры продолжают добавляться в ведро со скоростью CIR.

Пример

Рассмотрим пример с устройством, на котором работает алгоритм текущего ведра. Пусть размер «ведра» равен 10 кбайт, а согласованная скорость равна 3 кбайт/с. Допустим, что в момент времени t₁ «ведро» содержит 3500 маркеров. Пришедший в этот же момент времени пакет размером 1500 байт будет отправлен с исходящего интерфейса, поскольку его размер меньше числа маркеров в «ведре» (1500<3500). При этом из ведра удалится 1500 маркеров и останется 2000 маркеров. В момент времени t₂=t₁+100 мс в «ведро» добавится 300 маркеров (3000 м/с * 0,1 с = 300 м) и на входящий интерфейс поступит новый пакет (1500 байт). Данный пакет также будет передан с исходящего интерфейса, так как 1500<2000+300. Ещё через 100 мс (t₃) в «ведре» будет 2300—1500+300=1100 маркеров. Пришедший в данный момент пакет будет отброшен (1500>1100). Все пакеты, которые поступят на устройство между t₃ и t₄=t₃+400 мс, тоже будут отброшены, поскольку в «ведре» в течение этого промежутка будет недостаточно маркеров для их передачи. Если усреднить число переданных пакетов по времени, то мы получим среднюю согласованную скорость CIR=3 кбайта/с. Если пакетов не было длительное время («ведро» успело наполниться), то допускается передача всплеска, то есть пачки пакетов. Размер всплеска определяется количеством маркеров в «ведре». Максимальный размер всплеска определяется объёмом «ведра». Однако средняя скорость передачи не превышает CIR. Пакеты не удовлетворяющие согласованной скорости могут не отбрасываться, а буферизироваться. То есть перед алгоритмом трафик ставится в очередь и на вход алгоритма пакеты будут поступать из начала очереди.

Алгоритм с двумя вёдрами

В данном алгоритме используется два ведра, размеры которых могут быть разными. Скорости поступления маркеров тоже могут быть разными. Если скорости поступления маркеров одинаковы, то алгоритм работает следующим образом. Размер первого «ведра» равен CBS, размер второго ведра равен EBS. Если число маркеров в первом «ведре» больше или равно размеру пакета, то пакет передаётся без изменений, как и в случае с одним «ведром». При этом маркеры удаляются только из первого «ведра». Если число маркеров в первом «ведре» меньше размера пакета, то занимаются маркеры из второго «ведра». При этом пакет передаётся, но с пониженным приоритетом. Например, устройство может изменить значение поля DSCP в IP заголовке. В данном случае передача пакета увеличит реальную среднюю скорость и она будет больше CIR. То есть если канал свободен, то устройство, в принципе, может передать этот пакет по сети. Однако если на пути его следования встретится перегруженное устройство, то он будет удалён в первую очередь, поскольку имеет более низкий приоритет. Если для передачи пакета не хватает маркеров из второго «ведра», то пакет отбрасывается. Т.о. размер гарантированно передаваемого всплеска равен CBS, то есть пакеты, которые отправляются по маркерам первого «ведра», будут гарантированно переданы. Размер максимального всплеска определяется суммой объёмов обоих «вёдер» CBS+EBS. Однако часть пакетов такого всплеска передаётся с пониженным приоритетом. Это те пакеты, которые передаются по маркерам второго «ведра». И их доставка не гарантируется, поскольку далее по сети они следуют с пониженным приоритетом. Поведение устройства в том или ином случае может отличаться от описанного здесь.

Маркер

RFC 2697 (single rate three color marker) описывает механизм односкоростного трёхцветного маркера. Задача маркера — «покрасить» трафик (пакеты) в три цвета: зелёный, жёлтый и красный. А что делать с этими пакетами разного цвета определяет администратор, управляющий устройством. Зелёные пакеты — это те, для которых хватает маркеров из первого «ведра». Жёлтые — для которых не хватает маркеров из первого «ведра», но хватает из второго. Красные — для которых не хватает маркеров ни из первого, ни из второго «вёдер». Например, зелёные пакеты могут передаваться без изменений, жёлтые — с пониженным приоритетом, красные — отбрасываться.

Реализация

При реализации алгоритма «ведро» можно представить в виде буфера. Однако это совсем не обязательно. Роль буфера или «ведра» может выполнять время. Нужно просто знать момент времени, когда был отправлен предыдущий пакет (t_п), настоящий момент времени (t_н) и размер временно́го промежутка, который эквивалентен размеру пакета, — Δt. Для того чтобы передать пакет, «ведро» должно содержать количество маркеров по крайней мере не меньше размера пакета. Время, за которое набирается достаточное количество маркеров для передачи одного пакета, равно Δt=P/CIR, где P — размер пакета. Тогда для того, чтобы решить, отправить пакет или отбросить, нужно сравнить время t_н-t_п и Δt. Если t_н-t_п<Δt, то пакет отбрасывается, иначе передаётся, при этом t_п принимает новое значение (t_п=t_н).

Литература

• John Evans, Clarence Filsfils. Deploying IP and MPLS QoS for Multiservice Networks: Theory and Practice. — Morgan Kaufmann, 2007. — ISBN 0-12-370549-5.
• Ferguson P., Huston G. Quality of Service: Delivering QoS on the Internet and in Corporate Networks. — John Wiley & Sons, Inc., 1998. — ISBN 0-471-24358-2.
• Implementation of the token bucket algorithm in python  (неопр.). Дата обращения: 30 ноября 2013.